//给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。 
//
// 
//
// 提示： 
//
// 
// num1 和num2 的长度都小于 5100 
// num1 和num2 都只包含数字 0-9 
// num1 和num2 都不包含任何前导零 
// 你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式 
// 
// Related Topics 字符串 
// 👍 244 👎 0

package leetcode.editor.cn;

import common.util.MyUtil;

/**
 * Java：字符串相加
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P415_AddStrings {
    public static void main(String[] args) {
        Solution solution = new P415_AddStrings().new Solution();
        MyUtil.print(solution.addStrings("123", "956"));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    /**
     * 一次遍历
     * 时间复杂度 O(max(m,n))
     */
    class Solution {
        public String addStrings(String num1, String num2) {
            StringBuilder sb = new StringBuilder();
            // 进位值
            int pre = 0, v1, v2, vSum;
            int l1 = num1.length() - 1;
            int l2 = num2.length() - 1;
            char[] arr1 = num1.toCharArray();
            char[] arr2 = num2.toCharArray();
            while (l1 >= 0 || l2 >= 0) {
                v1 = l1 < 0 ? 0 : (arr1[l1--] - '0');
                v2 = l2 < 0 ? 0 : (arr2[l2--] - '0');
                vSum = v1 + v2 + pre;
                pre = vSum / 10;
                sb.append(vSum % 10);
            }
            if (pre == 1) {
                sb.append(pre);
            }
            return sb.reverse().toString();
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}
